#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
    char flag;
} TreeNode;

typedef struct StackNode {
    TreeNode *data;
    struct StackNode *next;
} StackNode;

void creatTree(TreeNode **T, char *data, int *index) 
{
    char ch;
    ch = data[(*index)++];
    if ('#' == ch) {
        *T = NULL;
    }
    else {
        *T = (TreeNode *)malloc(sizeof(TreeNode));  
        (*T)->data = ch;
        (*T)->flag = 0;
        creatTree(&((*T)->lchild), data, index);
        creatTree(&((*T)->rchild), data, index); 
    }
}

int isEmpty(StackNode *S)
{
    if (S->next == NULL) return 1;
    return 0;
}

void push(StackNode *S, TreeNode *T)
{
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    node->data = T;
    node->next = S->next; //此时有两种可能 这种写法真的好
    S->next = node;
}
 
StackNode *pop(StackNode *S)
{
    if (isEmpty(S)) return NULL;
    StackNode *del = S->next;
    S->next = del->next;
    return del;
}

StackNode *initStack() 
{
    StackNode *S = (StackNode *)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}

void preOrder(TreeNode *T) 
{
    TreeNode *node = T;
    StackNode *S = initStack();
    while (node || !isEmpty(S)) {
        if (node) {
            printf("%c ", node->data);
            push(S, node);
            node = node->lchild;
        } else {
            node = pop(S)->data;
            node = node->rchild;
        }
    }  
    putchar('\n');
}

/*
//1.根入
//2.循环 左孩子为空
//3.出栈访问 入栈右孩子
*/

void inOrder(TreeNode *T)
{
    TreeNode *node = T;
    StackNode *S = initStack(S);
    while (node || !isEmpty(S)) {
        if (node) {
            push(S, node);
            node = node->lchild;
        } else {
            node = pop(S)->data;
            printf("%c ", node->data);
            node = node->rchild;
        }
    }
    putchar('\n');
}
StackNode *getTop(StackNode *S) 
{
    if (isEmpty(S)) return NULL;
    StackNode *top = S->next;
    return top;
}

void posOrder(TreeNode *T)
{
    TreeNode *node = T;
    StackNode *S = initStack();
    while (node || !isEmpty(S)) {
        if (node) {
            push(S, node);
            node = node->lchild;
        } else {
            TreeNode *top = getTop(S)->data;
            if (top->rchild && top->rchild->flag == 0) {
                top = top->rchild;
                push(S, top);
                node = top->lchild;
            } else {
                top = pop(S)->data;
                printf("%c ", top->data);
                top->flag = 1;
            }
        }
    }  
    putchar('\n');
}

int main(void) 
{
    int index = 0;
    
    TreeNode *T;
    creatTree(&T, "AB#DF###CEG##H###", &index); //p141

    preOrder(T);
    inOrder(T);
    posOrder(T);
    printf("\n\nA B D F C E G H \nB F D A G E H C\nF D B G H E C A\n");
    return 0;
}